/***************************************************************************
 * This routine is taken from the book "The Data Compression Book 2nd edition" 
 * I corrected some printing error and added the routine to clean up the tree
 *                                                    modified by nalsas dai
 ***************************************************************************/


/*********************** Start of LZSS.C *********************** 
 * 
 * This is the LZSS module, which implements an LZ77 style compression 
 * algorithm. As implemented here it uses a 12 bit index into the 
 sliding 
 * window, and a 4 bit length, which is adjusted to reflect phrase 
 * lengths of between 2 and 17 bytes. 
 */ 

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <ctype.h> 
#include "bitio.h" 

/* 
 * Various constants used to define the compression parameters. The 
 * INDEX_BIT_COUNT tells how many bits we allocate to indices into the 
 * text window. This directly determines the WINDOW_SIZE. The 
 * LENGTH_BIT_COUNT tells how many bits we allocate for the length of 
 * an encode phrase. This determines the size of the look-ahead buffer. 
 * The TREE_ROOT is a special node in the tree that always points to 
 * the root node of the binary phrase tree. END_OF_STREAM is a special 
 * index used to flag the fact that the file has been completely 
 * encoded, and there is no more data. UNUSED is the null index for 
 * the tree. MOD_WINDOW() is a macro used to perform arithmetic on tree 
 * indices. 
 * 
 */ 
//#define INDEX_BIT_COUNT       12 
#define INDEX_BIT_COUNT       9
#define LENGTH_BIT_COUNT      4 
#define WINDOW_SIZE           ( 1 << INDEX_BIT_COUNT ) //here is 512
#define RAW_LOOK_AHEAD_SIZE   ( 1 << LENGTH_BIT_COUNT ) 
#define BREAK_EVEN            ( ( 1 + INDEX_BIT_COUNT + LENGTH_BIT_COUNT ) / 9 ) 

#define LOOK_AHEAD_SIZE       (RAW_LOOK_AHEAD_SIZE + BREAK_EVEN)
#define TREE_ROOT             WINDOW_SIZE 
#define END_OF_STREAM         0 
#define UNUSED                0 
#define MOD_WINDOW( a )       ( ( a ) & ( WINDOW_SIZE - 1 ) ) 

char *CompressionName = "LZSS Encoder"; 
char *Usage      = "in-file out-file\n\n"; 

/* 
 * These are the two global data structures used in this program. 
 * The window[] array is exactly that, the window of previously seen 
 * text, as well as the current look-ahead text. The tree[] structure 
 * contains the binary tree of all of the strings in the window sorted 
 * in order. 
 */ 

unsigned char window[WINDOW_SIZE ]; 

struct { 
	int parent; 
	int smaller_child; 
	int larger_child; 
}tree [WINDOW_SIZE + 1 ]; 



/* 
 * Since the tree is static data, it comes up with every node 
 * initialized to 0, which is good, since 0 is the UNUSED code. 
 * However, to make the tree really usable, a single phrase has to be 
 * added to the tree so it has a root node. That is done right here. 
 */ 
void InitTree(int r) 
{ 
	tree[ TREE_ROOT ].larger_child = r; 
	tree[ r ].parent = TREE_ROOT; 
	tree[ r ].larger_child = UNUSED; 
	tree[ r ].smaller_child = UNUSED; 
} 

/* 
 * This routine is used when a node is being deleted. The link to 
 * its descendant is broken by pulling the descendant in to overlay 
 * the existing link. 
 */ 
void ContractNode( int old_node, int new_node)
{ 
	tree[ new_node ].parent = tree[ old_node ]. parent; 
	if ( tree[ tree[ old_node ].parent ].larger_child == old_node ) 
		tree[ tree[ old_node ].parent ].larger_child = new_node; 
	else 
		tree[ tree[ old_node ].parent ].smaller_child = new_node; 
	tree[ old_node ].parent = UNUSED; 
} 

/* 
 * This routine is also used when a node is being deleted. However, 
 * in this case, it is being replaced by a node that was not previously 
 * in the tree. 
 */ 
void ReplaceNode( int old_node,int new_node )  
{ 
	int parent; 

	parent = tree[ old_node ].parent; 
	if ( tree[ parent ].smaller_child == old_node ) 
		tree[ parent ].smaller_child = new_node; 
	else 
		tree[ parent ].larger_child = new_node; 
	tree[ new_node ] = tree[ old_node ]; 
	tree[ tree[ new_node ].smaller_child ].parent = new_node; 
	tree[ tree[ new_node ].larger_child ].parent = new_node; 
	tree[ old_node ].parent = UNUSED; 
} 

/* 
 * This routine is used to find the next smallest node after the node 
 * argument. It assumes that the node has a smaller child. We find 
 * the next smallest child by going to the smaller_child node, then 
 * going to the end of the larger_child descendant chain. 
 */ 
int FindNextNode(int node ) 
{ 
	int next; 

	next = tree[ node ].smaller_child; 
	while ( tree[ next ].larger_child != UNUSED ) 
		next = tree[ next ].larger_child; 
	return( next ); 
} 

/* 
 * This routine performs the classic binary tree deletion algorithm. 
 * If the node to be deleted has a null link in either direction, we 
 * just pull the non-null link up one to replace the existing link. 
 * If both links exist, we instead delete the next link in order, which 
 * is guaranteed to have a null link, then replace the node to be 
 deleted 
 * with the next link. 
 */ 
void DeleteString(int p)
{ 
	int replacement; 

	if ( tree[ p ].parent == UNUSED ) 
		return; 
	if ( tree[ p ].larger_child == UNUSED ) 
		ContractNode( p, tree[ p ].smaller_child ); 
	else if ( tree[ p ].smaller_child == UNUSED ) 
		ContractNode( p, tree[ p ].larger_child ); 
	else { 
		replacement = FindNextNode( p ); 
		DeleteString( replacement ); 
		ReplaceNode( p, replacement ); 
	} 
} 

/* 
 * This where most of the work done by the encoder takes place. This 
 * routine is responsible for adding the new node to the binary tree. 
 * It also has to find the best match among all the existing nodes in 
 * the tree, and return that to the calling routine. To make matters 
 * even more complicated, if the new_node has a duplicate in the tree, 
 * the old_node is deleted, for reasons of efficiency. 
 */ 
int AddString(int new_node,int *match_position) 
{ 
	int i; 
	int test_node; 
	int delta; 
	int match_length; 
	int *child; 
	if ( new_node == END_OF_STREAM ) 
		return( 0 ); 
	test_node = tree[ TREE_ROOT ].larger_child; 
	match_length = 0; 
	for ( ; ; ) { 
		for ( i = 0 ; i < LOOK_AHEAD_SIZE ; i++ ) { 
			delta = window[ MOD_WINDOW( new_node + i ) ] - 
				window[ MOD_WINDOW( test_node + i ) ]; 
			if ( delta != 0 ) 
				break; 
		} 
		//  printf("i=%d match_length=%d\n",i,match_length);
		if ( i >= match_length ) { 
			match_length = i; 
			*match_position = test_node; 
			if ( match_length >= LOOK_AHEAD_SIZE ) { 
				ReplaceNode( test_node, new_node ); 
				return( match_length ); 
			} 
		} 
		if ( delta >= 0 ) 
			child = &tree[ test_node ].larger_child; 
		else 
			child = &tree[ test_node ].smaller_child;
		//   printf("*child is %d\n",*child); 
		if ( *child == UNUSED ) { 
			*child = new_node; 
			tree[ new_node ].parent = test_node; 
			tree[ new_node ].larger_child = UNUSED; 
			tree[ new_node ].smaller_child = UNUSED; 
			return( match_length ); 
		} 
		test_node = *child; 

	} 
} 

void treeclear()
{
	for(int i=0;i<WINDOW_SIZE + 1;i++)
		tree[i].parent=tree[i].larger_child=tree[i].smaller_child=UNUSED;
}

/* 
 * This is the compression routine. It has to first load up the look 
 * ahead buffer, then go into the main compression loop. The main loop 
 * decides whether to output a single character or an index/length 
 * token that defines a phrase. Once the character or phrase has been 
 * sent out, another loop has to run. The second loop reads in new 
 * characters, deletes the strings that are overwritten by the new 
 * character, then adds the strings that are created by the new 
 * character. 
 */ 
//void CompressFile(FILE *input,BIT_FILE *output,int argc, char *argv[])

/*int CompressFile(tIobuf  *input,BIT_FILE *output) 
  { 
  int i,totalbytes=0; 
  int c; 
  int look_ahead_bytes; 
  int current_position; 
  int replace_count; 
  int match_length; 
  int match_position;

  current_position = 1; 
  for ( i = 0 ; i < LOOK_AHEAD_SIZE ; i++ ) { 
//if ( ( c = getc( input ) ) == EOF )
c=input->getbyte();
if(input->isEof()) 
break; 
window[ current_position + i ] = (unsigned char) c; 
} 
//look_ahead_bytes = 1;
look_ahead_bytes = i; 
InitTree( current_position ); 
match_length = 0; 
match_position = 0; 
while ( look_ahead_bytes > 0 ) { 
if ( match_length > look_ahead_bytes ) 
match_length = look_ahead_bytes; 
if ( match_length <= BREAK_EVEN ) { 
replace_count = 1; 
OutputBit( output,1);totalbytes++; 
OutputBits( output,(unsigned long)window[ current_position ], 8 );totalbytes+=8;
} else { 
OutputBit( output, 0 ); totalbytes++;
OutputBits( output,(unsigned long)match_position, INDEX_BIT_COUNT );totalbytes+=INDEX_BIT_COUNT; 
OutputBits( output,(unsigned long)(match_length-(BREAK_EVEN + 1 )),LENGTH_BIT_COUNT );totalbytes+=LENGTH_BIT_COUNT; 
replace_count = match_length; 
} 
for ( i = 0 ; i < replace_count ; i++ ) 
{ 
DeleteString( MOD_WINDOW( current_position + LOOK_AHEAD_SIZE ) ); 
//if ( ( c = getc( input ) ) == EOF )
c=input->getbyte();
if(input->isEof()) 
look_ahead_bytes--; 
else 
window[ MOD_WINDOW(current_position + LOOK_AHEAD_SIZE) ]=(unsigned char) c; 
current_position = MOD_WINDOW( current_position + 1 ); 
if ( look_ahead_bytes ) 
match_length = AddString( current_position, &match_position ); 
} 
} 
OutputBit( output, 0 ); totalbytes++;
OutputBits(output,(unsigned long) END_OF_STREAM, INDEX_BIT_COUNT);totalbytes+=INDEX_BIT_COUNT;
// while ( argc-- > 0 ) 
//  printf( "Unknown argument: %s\n", *argv++ );
return (totalbytes+7)/8; 
}
 */

/* 
 * This is the expansion routine for the LZSS algorithm. All it has 
 * to do is read in flag bits, decide whether to read in a character or 
 * a index/length pair, and take the appropriate action. 
 */ 

//void ExpandFile(BIT_FILE *input,FILE *output,int argc,char *argv[])
/*int ExpandFile(BIT_FILE *input,tIobuf *output)
  { 
  int i; 
  int current_position; 
  int c; 
  int match_length; 
  int match_position;
  int totalbytes=0;
  current_position = 1;
  for ( ; ; ) { 
  if (c=InputBit( input ) ) {     
  c = (int)InputBits( input, 8 );
//putc( c, output );
output->putbyte(c);totalbytes++; 
window[ current_position ] = (unsigned char) c; 
current_position = MOD_WINDOW( current_position + 1 ); 
} else { 
match_position = (int) InputBits( input, INDEX_BIT_COUNT ); 
if ( match_position == END_OF_STREAM ) 
break; 
match_length = (int) InputBits( input, LENGTH_BIT_COUNT ); 
match_length += BREAK_EVEN; 
for ( i = 0 ; i <= match_length ; i++ ) { 
c = window[ MOD_WINDOW( match_position + i ) ]; 
//putc( c, output );
output->putbyte(c); totalbytes++;
window[ current_position ] = (unsigned char) c; 
current_position = MOD_WINDOW( current_position + 1 ); 
} 
} 
} 

return totalbytes;
// while ( argc-- > 0 ) 
//  printf( "Unknown argument: %s\n", *argv++ ); 
} */

/************************* End of LZSS.C *************************/ 
/*
   int main(int argc, char *argv[])
   {
   char *s;
   BIT_FILE *outfileb;
   FILE *outfile;
   FILE *infile;
   BIT_FILE *infileb;

   if (!strcmp(argv[1],"e")) {
   if(!(infile=fopen(argv[2],"rb"))) printf("open file error!");
   outfileb=OpenOutputBitFile(argv[3]);
   CompressFile(infile,outfileb,0,NULL);
   CloseOutputBitFile(outfileb);
   fclose(infile);       
   }
   else if(!strcmp(argv[1],"d")) {
   infileb=OpenInputBitFile(argv[2]);
   outfile=fopen(argv[3],"wb");
   ExpandFile(infileb,outfile,0,NULL);
   CloseInputBitFile(infileb);
   fclose(outfile);
   }
   else printf("please specific arguments correctly!");
//  fclose(outfile);
printf("done");
}
 */
